
import java.util.*;

public class c_java {
    /*递归实现数组的逆序打印*/

    public static void printArray(int[] array,int len) {
     if (len>0){
         System.out.println(array[len-1]);
         printArray(array,len-1);
     }
     return;
    }

    public static void main(String[] args) {
        int[] arr={1,3,5,7,9};
        printArray(arr,5);
    }



    /*第一个只出现一次的字符*/
    public int FirstNotRepeatingChar(String str) {
        HashMap<Character, Integer> mp = new HashMap<>();
        //统计每个字符出现的次数
        for(int i = 0; i < str.length(); i++)
            mp.put(str.charAt(i), mp.getOrDefault(str.charAt(i), 0) + 1);
        //找到第一个只出现一次的字母
        for(int i = 0; i < str.length(); i++)
            if(mp.get(str.charAt(i)) == 1)
                return i;
        //没有找到
        return -1;
    }

//    寻找数组的中心下标
    /*
    * */
    public int pivotIndex(int[] nums) {
        int sumLeft = 0, sumRight = Arrays.stream(nums).sum();
        for (int i = 0; i < nums.length; i++) {
            sumRight -= nums[i];
            // 若左侧元素和等于右侧元素和，返回中心下标 i
            if (sumLeft == sumRight)
                return i;
            sumLeft += nums[i];
        }
        return -1;
    }


    //奇偶数组
    public int[] sortArrayByParity(int[] nums) {
        int[] ret=new int[nums.length];
        int left=0;
        int right=ret.length-1;
        for (int i: nums) {
            if (i%2==0){
                ret[left++]=i;
            }else {
                ret[right--]=i;
            }
        }
        return ret;
    }
    /*给你一个字符串 s ，根据下述规则反转字符串：*/

    /*给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。*/
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
//统计最后一个单词的长度
    public int lengthOfLastWord(String s) {
        char[] ch=s.toCharArray();
        boolean flg=false;
        int count=0;
        for (int i = ch.length-1; i >=0; i--) {
            if (ch[i]==' '&&flg){
                break;
            }else {
                if (ch[i]!=' '){
                    count++;
                    flg=true;
                }
            }
        }
        return count;
    }
    /*给定两个有序【升序的】整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有
序数组*/
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int j=0;
        for (int i = m; i <m+n ; i++) {
            nums1[i]=nums2[j];
            j++;
        }
        Arrays.sort(nums1);
    }

//    给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
    public static boolean isPalindrome(int x) {
        int y=0;
        int x1=x;
        while (x>0){
            y =y*10+(x%10);
            x/=10;
        }
        if (y==x1)return true;
        return false;
    }

    public static void main17(String[] args) {
       boolean ret= isPalindrome(121);
        System.out.println(ret);
    }

//    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
//    请必须使用时间复杂度为 O(log n) 的算法。
    public static int searchInsert(int[] nums, int target) {
        //二分查找
        int left=0;
        int right=nums.length-1;
        int mid=0;
        while (left<=right){
            mid=(left+right)/2+1;
            if (nums[mid]==target){
                return mid;
            }else if (nums[mid]>target){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        if (nums[mid]<target){
            return mid+1;
        }else {
            return mid;
        }
    }

    public static void main16(String[] args) {
        int[] nums={1,3};
        searchInsert(nums,2);
    }


    /* 给定一个数组 nums 和一个值 val ，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
   不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成*/
    //官话解法
    public int removeElement1(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
    public int removeElement(int[] nums, int val) {
        int size=nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val){
                if (i == nums.length-1){
                    size--;
                    nums[i]=0;
                }
                else{
                    for (int j = i; j < nums.length-1; j++) {
                        nums[j]=nums[j+1];
                    }
                    nums[size-1]=val+1;//防止出现最后一个还是等于val值的元素
                    size--;
                    i--;
                }
            }
        }
        return  size;

    }
    /*******************************************************************************/
//    给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }
    /*******************************************************************************/
    //将大写字母转换为小写
    public String toLowerCase(String s) {
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)>='A'&&s.charAt(i)<='Z'){
                sb.append((char)(s.charAt(i)+32));
            }else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();

    }
    /*******************************************************************************/
    //数字符串有多少个数字
    public static int isNumeric(String str){
        int count=0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i)>=0&&str.charAt(i)<=9){
                count++;
            }
        }
        return count;
    }
    /*******************************************************************************/
    public static String test4(String str) {
     /*   将用户输入的字符串转化（压缩）。
        例如： "aabbccdaa" -> "a2b2c2d1a2" 或者 例如： "abbcccffr" -> "a1b2c3f2r1"*/
        //1:直接使用map直接创建一个数组对应的
        //2:创建数组解决
        int pos = 0;	//记录比较的位置
        int count = 1;	//计数相同字符的数量
        char[] chs = str.toCharArray();	//将传入的字符串转换成字符数组
        char temp;	//记录当前正在做计数工作的字符
        StringBuffer sb = new StringBuffer();	//存放压缩后的字符串的StringBuffer，这里我们需要使用appened()方法来逐步追加来完成压缩后的字符串的构建，所以使用了StringBUffer
        for(int i= 0; i <= chs.length-1; i = pos + 1){
            temp = chs[i];
            pos = i;
            count = 1;
            while(pos < chs.length-1 && chs[pos] == chs[pos+1]){//遍历字符数组，直到结束或者遇到不同的
                count++;
                pos++;
            }
            if(count > 0){	//计数结果两个以上追加数字
                sb.append(temp);
                sb.append(count);
            }
        }
        return sb.toString();	//将StringBUffer转换成字符串返回
    }

    public static void main15(String[] args) {
       String str= test4("aabbccdaa");
        System.out.println(str);
    }











    /*******************************************************************************/
    public static String reverseSentence(String str) {
//        字符串逆置，如 "I am a student" 逆置为 "student a am I"
        Stack<String> stack=new Stack<>();
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i)==' '|| (i==(str.length()-1))){
                sb.append(' ');
                stack.push(sb.toString());
                sb=new StringBuilder();
            }else{
                sb.append(str.charAt(i));
            }
        }
        StringBuilder sb2=new StringBuilder();
        while (!stack.isEmpty()){
            sb2.append(stack.pop());
        }
        return sb2.toString();
    }
    public static void main14(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String string2 = scanner.nextLine();

        System.out.println(reverseSentence(string2));
    }



    /*******************************************************************************/
    public static void LeftRotateString(String str,int n){
       /* 将一个字符串从左开始前k个字符进行旋转：左旋数组 。例如字符串："abcdef"，前2个左旋结果
        是："cdefab"*/
        StringBuilder sb=new StringBuilder();
        int k=n;
        while (n<str.length()){
            sb.append(str.charAt(n));
            n++;
        }
        for (int i = 0; i < k; i++) {
            sb.append(str.charAt(i));
        }
        System.out.println(sb.toString());
    }

    public static void main13(String[] args) {
        LeftRotateString("abcdef",2);
    }

    /*******************************************************************************/
   /* public static void fnid_val(int [][]arr,int row,int col,int num) {
      *//*  在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成
        一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。时间复杂度小于O(n) ,空间复杂度
        O(1)*//*

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {

            }
        }

    }*/
    public static void main12(String[] args) {
        int [][]array = {
                {1,2,8,9},
                {2,4,9,12},
                {4,7,10,13},
                {6,8,11,15}
        };
        //fnid_val(array,3,3,10);
    }


    /*******************************************************************************/
    public static int[] findNumberAppearOnce(int[] arr) {
//        一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if ((arr[i]^arr[j])==0){
                    arr[i]=0;
                    arr[j]=0;
                    break;
                }
            }
        }
        return arr;
    }

    public static void main11(String[] args) {
        int[] arr={1,1,2,2,3,5};
        findNumberAppearOnce(arr);
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]!=0){
                System.out.println(arr[i]);
            }
        }
    }



    /*******************************************************************************/
    public static boolean isPower(int n){
        /*如何判断一个数是否是2的k次方？这里不需要确定k的值。例如：1是2的0次方，2是2的1次方，4是2的平方，
        求N是不是2的K次方？*/
        int i = 1;
        for (; i <n ; i*=2) {
        }
        if (i==n)return true;
        return false;
    }
    public static void main10(String[] args) {
        System.out.println(isPower(256));
    }
    /*******************************************************************************/
    public static int Sum(int[] array,int n){
        if(n==0)//基线条件
            return 0;
        else{
            int len=n-1	;
            if (len==0){
                return array[len];
            }else{
                return array[len]+Sum(array,n-1);
            }

        }
    }
    public static void main9(String[] args) {
//        编写一个递归程序，求一个一维数组的所有元素的和？
        int[] arr={1,2,3,4,5};
        int count=Sum(arr,arr.length);
        System.out.println(count);
    }
    /*******************************************************************************/
    public static boolean panD(int a,int b){
        if (a==b)return false;
        int count=0;
        for (int i = 1; i < b/2+1; i++) {
            if (b%i==0){
                count+=i;
            }
        }
        if (count==a){
            return true;
        }
        return false;
    }
    public static void main8(String[] args) {
//        一对相亲数是指：甲的约数之和等于乙，乙的约数之和等于甲。求1000以内的相亲数

        for (int i = 1; i < 1000 ; i++) {
            int count=0;
            for (int j = 1; j <i/2+1 ; j++) {
                if (i%j==0){
                   count+=j;
                }
            }
            if (panD(i,count)){//判断是不是相亲数
                System.out.println(i+" "+count);
            }
        }

    }
    /*******************************************************************************/
    public static void main7(String[] args) {
//        给定一个3乘以3的二维数组，里面的数据随机生成。分别求出两个对角线的元素之和。
        int[][] array=new int[3][3];
        int count=0;
        for (int i = 0; i < 3; i++) {
            count+=array[i][i]+array[i][3-i-1];
        }

    }







    /*******************************************************************************/
    public static int getAge(int age){
        /*有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三
        个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多
        大？*/
        int count=10;
        for (int i = 0; i < 5; i++) {
            count+=2;
        }
       return count;
    }

    public static void main6(String[] args) {
        System.out.println(getAge(10));
    }



    /*******************************************************************************/
    public static int fun(int n){
        //斐波那契问题
        /*有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子
        都不死，问第n个月的兔子对数为多少？*/
        int a=1;
        int b=1;
        int c=0;
        while (n>2)
        {
            c = a + b;
            a = b;
            b = c;
            n--;
        }
        return c;
    }





    /*******************************************************************************/
    public static void main5(String[] args) {
        /*一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在 第10次落地时，共经过多 少
        米？第10次反弹多高？*/
        int mi=100;
        int count=0;
        for (int i = 0; i < 10; i++) {
            count+=mi;
            mi/=2;
        }
        System.out.println("共经过多少米："+count+" 第10次反弹多高："+mi);
    }

    /*******************************************************************************/
    public static void main4(String[] args) {
        /*猴子吃桃问题。猴子第一天摘下若干个桃子，当时就吃了一半，还不过瘾，就又吃了一个。第二天又将剩下的
        桃子吃掉一半，又多吃了一个。以后每天都吃前一天剩下的一半零一个。到第 10 天在想吃的时候就剩一个桃子了,
         求第一天共摘下来多少个桃子？*/
        int count=1;
        for (int i = 1; i < 10 ; i++) {
            count=(count+1)*2;
        }
        System.out.println(count);
    }


    /*******************************************************************************/
    public static boolean perfectNumber(int num ){
       /* 编程求 1~10000 之间的所有“完全数”，完全数是该数的所有因子之和等于该数的数。例如，6 的因子有 1、2、
        3，且 6=1+2+3，所以 6 是完全数*/
        if (num%2!=0)return false;
        List<Integer> list=new ArrayList<>();
        for (int i = 1; i < num/2+1; i++) {
            if (num%i == 0){
                list.add(i);
            }
        }
        int bj=0;
        for (int i = 0; i < list.size(); i++) {
            bj+=list.get(i);
        }
        if (bj==num){
            return true;
        }
        return false;
    }

    public static void main3(String[] args) {
        for (int i = 1; i < 10000; i++) {
            if (perfectNumber(i)){
                System.out.println(i);
            }
        }
    }
    /*******************************************************************************/
    //        编写程序，对输入的年、月、日，给出该天是该年的第多少天？
    public static   void isDays(int year,int month,int day) {
        int count=0;
        for(int i=1;i<month;i++){
            switch(i){
                case 1: case 3: case 5: case 7: case 8: case 10: case 12:
                    count+=31;
                    break;
                case 4: case 6: case 9: case 11:
                    count+=30;
                    break;
                case 2:
                    //判断是不是闰年
                    if((year % 4 == 0 && year%100 != 0)|| (year % 400 == 0)){
                        count += 29;
                    }else{
                        count += 28;
                    }
            }

        }
        System.out.println(year+"年"+month+"月"+day+"日，是该年得第"+(count+day)+"天");
    }
    public static void main2(String[] args) {
        isDays(2022,2,15);

    }
    /*******************************************************************************/
    public static void main1(String[] args) {
        //1:编写程序，输入一个字符，判断它是否为小写字母，如果是，将它转换成大写字母，否则，不转换
        Scanner sc=new Scanner(System.in);
        /*String str=sc.nextLine();
        //第一种方法
        str=str.toLowerCase(Locale.ROOT);
        System.out.println(str);*/
        //第二种方法
        String str2=sc.nextLine();
        char[] chars=str2.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i]>=65&&chars[i]<=90){
                chars[i]= (char) (chars[i]+32);
            }
        }
    }
}
